package cn.whdream.datastructure.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 
 * @author admin
 * 逆波兰表达式 中缀转后缀表达式
 */
public class PolandNotation2 {
	public static void main(String[] args) {
		//String suffixExpression = "30 4 + 5 * 6 - ";
		String intoFixExpression = "1 + ( ( 2 + 3 ) * 4 ) - 5";
		String[] temp = intoFixExpression.split(" ");
		List<String> list = convertSuffixExpression(new ArrayList<String>(Arrays.asList(temp)));
		System.out.println(list);
		int res = calculateExpression(list);
		System.out.printf(intoFixExpression +"= %d",res);
	}

	private static List<String> convertSuffixExpression(List<String> arrayList) {
		System.out.println("arr"+arrayList);
		List<String> result = new ArrayList<>();
		Stack<String> s1 = new Stack<>();
		for (String item : arrayList) {
//			System.out.println("item-->"+item);
//			System.out.println("result s2-->"+result);
//			System.out.println("s1-->"+s1);
			//判断为数字
			if (item.matches("\\d+") ) {
				result.add(item.trim());
			}else {//不为数字
				// 1.s1为空 2.输入的 item为 “（” 3.顶部符号为 “（”；则都将元素放入
				if (s1.empty()||item.equals("(") ||s1.peek().equals("(")) {
					s1.push(item);
					continue;
				}
				//如果扫描的 右括号
				if (item.equals(")")) {
					//遍历s1将非左括号前的符合全部先要入 s2中
					while(!s1.empty()) {
						if (s1.peek().equals("(")) {
							s1.pop();
							break;
						}else {
							result.add(s1.pop());
						}
					}
					continue;
				}
				//遇到运算符
				char ch = item.charAt(0);
				int currentItemPriority = getPriority(ch);
				while(true) {
					//为空直接入栈
					if (s1.empty()) {
						s1.push(item);
						break;
					}
					int headPriority = getPriority(s1.peek().charAt(0));
					//对比 栈内优先级高，则直接入栈
					if (currentItemPriority > headPriority) {
						s1.push(item);
						break;
					}else {
						//低则先将优先级高的放入result,然后重新和栈中元素对比
						String topValue = s1.pop();
						result.add(topValue);
					}
				}
			}
		}
		//将s1中的元素，依次放入 result
		while (!s1.empty()) {
			result.add(s1.pop());
		}
		System.out.println("final result"+result);
		return result;
	}
	//计算表达式中的内容
	private static int calculateExpression(List<String> list) {
		Stack<Integer> stack = new Stack<>();
		for(String s:list) {
			if (s.matches("\\d+")) {
				stack.push(Integer.parseInt(s));
			}else {
				int num1 = stack.pop();
				int num2 = stack.pop();
				int res = calculate(num1, num2, s.charAt(0));
				stack.push(res);
			}
		}
		return stack.pop();
	}
	
	private static int calculate(int num1, int num2, int oper) {
		switch (oper) {
		case '+':
			return num1 + num2;
		case '-':
			return num2 - num1;
		case '*':
			return num1 * num2;
		case '/':
			return num2 / num1;	
		default:
			return 0;
		}
	}
	
	private static int getPriority(char stackHead) {
		if (stackHead == '*' || stackHead == '/') {
			return 1;
		}else if (stackHead == '+' || stackHead == '-') {
			return 0;
		}
		return -1;
	}
}
